package leetcode.editor.cn;
//DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。 
//
// 
// 例如， "ACGAATTCCG" 是一个 DNA序列 。 
// 
//
// 在研究 DNA 时，识别 DNA 中的重复序列非常有用。 
//
// 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
//输出：["AAAAACCCCC","CCCCCAAAAA"]
// 
//
// 示例 2： 
//
// 
//输入：s = "AAAAAAAAAAAAA"
//输出：["AAAAAAAAAA"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 105 
// s[i]=='A'、'C'、'G' or 'T' 
// 
// Related Topics 位运算 哈希表 字符串 滑动窗口 哈希函数 滚动哈希 
// 👍 469 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution59 {
    public List<String> findRepeatedDnaSequences(String s) {
        int[] nums = new int[s.length()];
        for (int i = 0; i < nums.length; i++) {
            switch (s.charAt(i)) {
                case 'A':
                    nums[i] = 0;
                    break;
                case 'C':
                    nums[i] = 1;
                    break;
                case 'G':
                    nums[i] = 2;
                    break;
                case 'T':
                    nums[i] = 3;
                    break;
                default:
                    break;
            }
        }

        // 代表四个不同数字
        int R = 4;
        // 十位相同字符
        int L = 10;

        int RL = (int) Math.pow(R, L - 1);
        HashSet<String> res = new HashSet<>();
        HashSet<Integer> sets = new HashSet<>();
        int left = 0;
        int right = 0;
        int window = 0;
        while (right < s.length()) {
            window = window * R + nums[right];
            right++;

            if (right - left == L) {
                if (sets.contains(window)) {
                    res.add(s.substring(left, right));
                } else {
                    sets.add(window);
                }
                window = window - nums[left] * RL;
                left++;
            }
        }
        return new LinkedList<String>(res);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
